1. Field of the Invention
The present invention relates to a microprocessor capable of preventing illegal alteration of execution codes and processing target data under a multi-task program execution environment.
2. Description of the Related Art
The open system in which hardware information of a computer for general user such as PC and system program information of the operation system (OS) are disclosed rather than being concealed is widely spread today. In the open system, the end-user can make any desired improvement by modifying the system program.
Under such a circumstance, in order to guarantee the copyright protection for data handled by application programs or the copyright protection for programs themselves, there is a need for hardware with a secret protection capability which is based on the presumption that the OS of the system can carry out hostile operations with respect to applications. Such hardware with a secret protection capability has been proposed especially in a form of a microprocessor (see commonly assigned co-pending U.S. patent application Ser. No. 09/781,158 and No. 09/781,284; and Lie et al., “Architectual Support for Copy and Tamper Resistant Software”, Computer Architecture News 28(5), pp. 168-).
Such a microprocessor with a secret protection capability has a function for encrypting a program and data handled by that program under the multi-task environment in order to protect them from the peeping and the alteration. In the following, such a microprocessor will be referred to as a tamper resistant microprocessor.
The main purpose of the tamper resistant microprocessor is to protect the rights of the copyright owners of programs, contents and network services by protecting applications operated on the end-user's system. More specifically, three major concerns are (1) the protection of algorithms implemented in programs, (2) the protection of trade secrets and contents embedded in programs, and (3) the protection of the program operations from the alteration.
The protection of algorithms implemented in programs is necessary in order to protect the copyright owners of the programs. The protection of the trade secrets embedded in programs is necessary in order to prevent illegal copies of contents handled by the programs. The protection from the illegal alteration is necessary in order to protect the rights of the service providers, for example.
In the application in which a program that utilizes a network service exchanges a charging information with a server, it is particularly important to prevent the illegal alteration so that the charging information transmission operation is executed properly. As a practical example, it is well known that a program for reproducing DVD on PC was analyzed to obtain the trade secret for decrypting the encryption of DVD and a program (DeCSS) for illegally copying DVD was produced.
In the open system, mechanisms for simply protecting secrets of the application programs have been proposed conventionally, and the present inventors have been proposing a protection environment for protecting secrets independently from the OS that manages the system resources, for each one of a plurality of programs (programs from a plurality of different program vendors or a plurality of different programs from a single vendor) that are to be operated in a pseudo-parallel manner on a single system (see commonly assigned co-pending U.S. patent application Ser. Nos. 09/781,158, 09/781,284, 09/984,407 and 10/059,217, for example). Such a protection environment will be referred to as a “multi-party application protection environment”.
FIG. 18 shows a general multi-party application protection environment. In FIG. 18, an exemplary case where a user 12 purchases a program from a vendor-1 21-1 among a plurality of software vendors 21-1 to 21-n will be considered. A system 2 used by the user 12 has a built-in microprocessor, and this processor-A 3 has a secret key-A 5 unique to this processor. A public key-A 13 corresponding to the secret key-A is disclosed to the public.
The software vendor-1 develops a program 22-1, selects a program key-1 24-1 as an encryption key, and produced an encrypted program 23-1 by encrypting a plaintext program 22-1. Then, the software vendor-1 produces a distribution key-1 25-1 by encrypting the program key-1 by using the public key-A unique to the processor-A of a distribution target system 2.
Although not shown in the figure, the software vendor-1 also develops a plurality of different programs besides the program 22-1, selects program keys for respective programs, and produces encrypted programs and distribution keys. Here, only a single program will be described for the sake of explanation.
The software vendor-1 delivers the encrypted program 23-1 and the encrypted distribution key 25-1 to the target system 2 through a network. The delivered program 23-1 and distribution key 25-1 are stored into a secondary memory (a hard disk, for example) of the system. The program 23-1 contains execution codes and data (initialization data, etc.) and at a time of the execution, they are read out in the encrypted state to an external memory 8 provided outside of the microprocessor 3. The encrypted program on the external memory 8 will be referred to as a protected program.
The microprocessor-A reads the distribution key 25-1, and decrypts it by using the secret key-A corresponding to the public key-A to obtain the program key-1. The key decryption processing is carried out at a protection logic 6 inside the microprocessor.
Next, the microprocessor-A decrypts the program-1 by using the program key-1 and reads it into a cache memory 4. The decryption and the reading into the cache memory 4 is realized by a prescribed caching algorithm according to the execution of the program, for each part separately, so that the entire program is not read into the cache memory 4 at once. The program read into the cache memory 4 is in the plaintext state, so that it is executed at the core 6 similarly as the ordinary non-encrypted programs. A part for handling the program key-1 and the plaintext programs is executed by the core 6 of the processor-A, and there is no room for the OS to intervene. The contents of the cache memory 4 and the secret key 5 provided in the microprocessor cannot be read out directly from the external, except for the operations defined by the processor specification.
Note that, although not shown in the figure, for the plaintext information stored in the cache memory 4, an identifier for identifying the encryption key used in decrypting that plaintext information is attached to each line of the cache memory 4, in order to guarantee that the secret is maintained independently among programs even when the user purposes a plurality of different programs from a plurality of program vendors 21-1 to 21-n. The program keys are different for different programs of different program vendors so that the independence of the program can be guaranteed by setting a task of the cache line and the key used for decrypting it in correspondence.
Now, the problems to be solved by the present invention are as follows.
(1) In order to realize the task identification function, there is a need to have a table for maintaining the program key of each program in correspondence to the task ID, inside the microprocessor. The setting of such a table will be commanded by the OS that manages the system, so that there is a need to provide a function for operating the table from the OS program. This table operation function obviously must satisfy the secret protection requirement.
Also, the task corresponding key table plays a central role in the secret protection, but due to the finiteness of resources and the consideration of costs, it is impossible to increase the capacity of the table indefinitely. For this reason, which programs should be allocated with the entries of the table and how to re-utilize the entries must be managed by the OS according to the intention of the system user.
Such operations of the OS have a possibility of introducing a defect into the secret protection. For example, in a state where the task ID #1 is allocated to some program key X, suppose that the OS re-allocates the same task ID #1 to another program key Y. In this case, if the cache line to which the tag of the task ID #1 is assigned remains in the cache memory, this data can be read out from the program corresponding to the program key Y. This is in violation of the principle of the secret protection.
Thus, the first problem to be solved is to provide a task state management and table management mechanism for preventing such a violation.
(2) There are two types of the program encryption methods including a method in which the decryption processing is completed in units of cache lines, and a method in which data of a plurality of cache lines are required for the decryption of one cache line. The former method does not influence the memory capacity and the interchange in units of lines, but the latter method is associated with the following problems.
In the method in which data of a plurality of cache lines are required for the decryption of a cache line, when the random access to the memory occurs, there is a need to read the memory regions in front and behind of the required memory region. For this reason, a large overhead will be caused.
Also, as the decryption result depends on data of the neighboring lines, there is a possibility of the so called block interchange attack. The block interchange attack is an attack in which an attacker appropriately interchanges the block information encrypted according to the same secret so as to change the system state according to the intention of the attacker. For example, suppose that the attacker learns that a line P arranged at some address X is a portion corresponding to the charging operation, from the timing of the communication or the like. Then, suppose that the attacker also knows that the service provided by the program is not adversely affected even when another line Q that is encrypted by using the same program key is executed. In this case, when the line P is replaced by the line Q, the attacker can escape just the charging without affecting the service of the program. The similar attack is also applicable to data handled by the program.
The above problem can be resolved if a separate key is given to every block, but if the separate encryption key for each block is stored in the distribution key, the algorithm for encrypting the distribution key by using the public key becomes enormous, and causes the overhead in the decryption processing. Also, there arises a need to provide a table with an enormous capacity for managing such keys inside the microprocessor, so that it is not practical from viewpoints of the key distribution and the management cost.
In addition, the general program does not necessarily always have a predetermined address at which it is to be arranged, and the address at which it is to be arranged can be changed depending on a configuration of the target system (a configuration of the library and the shared memory to be shared with the other programs). This is called re-location. In the case of carrying out the encryption for each block, the problem of the re-location must be taken into account.
Thus, the second problem to be solved is to provide a microprocessor which has a small processing overhead, which makes the data interchange attack difficult, and which has a secret information management capability that accounts for the re-location.
(3) Three elements that constitute the application are a program (execution codes), data, and context information, but they are handled differently inside the processor. The execution codes and the data comprises the main body of the program, while the context is a state information to be saved on a memory for the purpose of resuming the task after the execution of the task is interrupted.
In general, the program inside the microprocessor will not be rewritten, but when data on the cache is changed, the data will be written back to the external memory.
Also, the program and the data are accessed in units of cache lines, but the context information often takes a size that cannot be stored into a single cache line. At a time of the context switching, information over a plurality of cache lines will be collectively read or written.
In exchanging these informations with different properties with the external memory, the separate encryption processings will be required, but the reduction of the hardware cost is also demanded.
Thus, the third problem to be solved is to provide a microprocessor that can commonly use the same encryption processing hardware for these informations.